类比十进制下的纯循环小数, 进制下的纯循环小数满足最简分数分母与 互质。
而题目要求相同数值只计数一次,所以只需要考虑最简分数的情况。
那么答案为:
后面的求和跟原来的形式相同 , 令
那么:
或 时 。
时
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN = 1e6;
int n , m , k;
int num , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , summ[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) { prime[ ++ num ] = i; mu[ i ] = -1; }
for( int j = 1 ; j <= num && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
for( int i = 1 ; i <= MAXN ; i ++ ) summ[ i ] = summ[ i - 1 ] + mu[ i ];
}
map< int , int > Mapm;
int Summu( int n ) {
if( n <= MAXN ) return summ[ n ];
if( Mapm[ n ] ) return Mapm[ n ];
int Ans = 1;
for( int l = 2 , r ; l <= n ; l = r + 1 ) {
r = n / ( n / l );
Ans -= ( r - l + 1 ) * Summu( n / l );
}
return Mapm[ n ] = Ans;
}
LL f( int n , int m , int k ) {
if( !n || !m ) return 0;
if( k == 1 ) {
long long Ans = 0;
for( int l = 1 , r ; l <= min( n , m ) ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans += 1ll * ( Summu( r ) - Summu( l - 1 ) ) * ( n / l ) * ( m / l );
}
return Ans;
}
long long Ans = 0;
for( int d = 1 ; d <= k ; d ++ )
if( k % d == 0 && mu[ d ] ) Ans += mu[ d ] * f( m / d , n , d );
return Ans;
}
int main( ) {
sieve( );
scanf("%d %d %d",&n,&m,&k);
printf("%lld\n", f( n , m , k ) );
return 0;
}